package leetcode.N1_N100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/9/10 10:08 上午
 *
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的每个数字在每个组合中只能使用一次。
 *
 * 说明：
 *
 * 所有数字（包括目标数）都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1:
 *
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 所求解集为:
 * [
 *   [1, 7],
 *   [1, 2, 5],
 *   [2, 6],
 *   [1, 1, 6]
 * ]
 * 示例 2:
 *
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 所求解集为:
 * [
 *   [1,2,2],
 *   [5]
 * ]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 */
public class N40 {

    public static void main(String[] args) {
        int[] candidates = {2,5,2,1,2};
        int target = 5;

        List<List<Integer>> lists = combinationSum(candidates, target);
        System.out.println(lists);
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 先让数组变有序
        Arrays.sort(candidates);
        // 定义解集
        List<List<Integer>> answers = new ArrayList<>();
        // 调用路径搜索算法
        int lastRoot = -1;
        for (int i = 0; i < candidates.length; i++) {
            int currentRoot = candidates[i];
            if (lastRoot == currentRoot) {
                continue;
            } else {
                lastRoot = currentRoot;
            }
            dfs(candidates, i, target, answers, new ArrayList<>());
        }
        // 返回结果
        return answers;
    }

    private static void dfs(int[] candidates, int index, int target, List<List<Integer>> answers, List<Integer> currentAnswer) {
        if (target <= 0) {
            return;
        }
        if (index >= candidates.length) {
            // 超出边界 当前路径无解 退出
            return;
        }
        int candidate = candidates[index];
        if (candidate > target) {
            // 由于是从小到大遍历  如果当前数已经大于目标值 则后续值也必然大于目标值 当前路径无解 退出
            return;
        }
        if (candidate == target) {
            // 加入当前值就是解 则加入解集
            currentAnswer.add(candidate);
            answers.add(currentAnswer);
            return;
        }
        // 当前未到末路 继续前进
        currentAnswer.add(candidate);
        // 从下一个 逐个迭代往后走
        for (int i = index + 1; i < candidates.length; i++) {
            dfs(candidates, i, target - candidate, answers, new ArrayList<>(currentAnswer));
        }
    }

}
